Statement#

Given a robot located at the top-left corner of an m×nm \times n matrix, determine the number of unique paths the robot can take from start to finish while avoiding all obstacles on the matrix.

The robot can only move either down or right at any time. The robot tries to reach the bottom-right corner of the matrix.

An obstacle is marked as 1, and an unoccupied space is marked as 0 in the matrix.

Constraints:

  • m ==== matrix.length

  • n ==== matrix[i].length

  • matrix[i][j] is either 1 or 0

  • 11 \leq m, n 450\leq 450

Example#

No.

Matrix

Unique Paths

1

[

[0, 0, 0],

[0, 0, 0],

[0, 0, 0]

]

6

2

[

[0, 0, 0],

[0, 1, 0],

[0, 0, 0]

]

2

3

[

[0, 0, 0],

[1, 1, 1],

[0, 0, 0]

]

0

Try it yourself#

Implement your solution in the following playground.

Python
usercode > main.py
Input #1
Unique Paths to Goal

Note: If you clicked the "Submit" button and the code timed out, this means that your solution needs to be optimized in terms of running time.

Hint: Use dynamic programming and see the magic.

Solution#

We will first explore the naive recursive solution to this problem and then see how it can be improved using the Recursive Number pattern.

Naive approach#

A naive approach is to find all the possible unique paths by traversing the array from start to finish. Every time, we need to check if we have reached the bottom-right corner of the matrix or if the iterating index exceeds the size of the matrix. If this condition is satisfied, we just stop the iteration here. If an obstacle is present in the array, the number of unique paths will be 0 up to that obstacle. After that, we will traverse to the next cell in the row and the column finding all the possible unique paths.

For example, we have the following matrix:

  • Matrix: [ [0, 0], [1, 0] ]

We will use the recursive approach to find the unique number of paths up to the bottom-right corner of the matrix. For this, we will try all the possible paths and get only one solution which is moving right and then bottom to reach the bottom-right corner.

  • Number of Unique Paths: 1

Let’s implement the algorithm as discussed above:

Unique Paths to Goal using recursion

Note: Please observe that if you include the test case commented out in the driver code, the solution is likely to time out. Try to solve the larger problem using the dynamic programming solutions provided below and see the difference.

Time complexity#

The time complexity of this solution is O(2m×n)O(2 ^ {m \times n}). This is because there are always two possibilities to move, either down (next row) or right (next column), where mm and nn are the rows and columns for the input matrix.

Space complexity#

The time complexity of this solution is O(m×n)O(m \times n), where mm and nn are the rows and columns for the input matrix.

Optimized solution using dynamic programming#

Now, let’s improve the recursive solution using top-down and bottom-up approaches.

Top-down solution#

The top-down solution, commonly known as the memoization technique, enhances the recursive solution. It overcomes the problem of calculating redundant solutions over and over again by storing them in an array. In this algorithm, we will create a 2-D array in which each cell will contain all the possible unique paths to reach itself. So when computing the unique paths to the next cell, we will use the stored values of the previous cell instead of computing them again. The value in the finish cell will be the number of unique paths to that cell.

Let’s implement the algorithm as discussed above:

Unique Paths to Goal using memoization

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

The time complexity of this solution is O(m×n)O(m \times n), where mm and nn are the rows and columns for the input matrix.

Space complexity#

The space complexity of this solution is O(m×n)O(m \times n), where mm and nn are the rows and columns for the input matrix.

Bottom-up solution#

The bottom-up solution, also known as the tabulation technique, is an iterative method of solving dynamic programming problems. Here we again create a 2-D array of the same size as the matrix given. In the bottom-up approach, we start moving through the rows and filling in the values. If an obstacle (1) is found at any place, we will set the value of that cell to 0 because we cannot reach that place, so unique paths will be 0. Starting with the base condition, we will set the values of the first row and column to 1 if no obstacles are found. Now we will start traversing row-wise, if there is no obstacle, then the answer will be the sum of the values of the top and left cells, and if there is an obstacle, we will just insert the value 0 to that cell irrespective of the values of other cells.

Let’s look at the following illustration to get a better understanding of the solution:

Created with Fabric.js 3.6.6 Lets start from the 1st cell.

1 of 18

Created with Fabric.js 3.6.6 The 0 indicates that the cell does not have an obstacle, so the robot can passthrough this cell.So, we set the value of the cell to 1, indicatingthat there is 1 path through it.

2 of 18

Created with Fabric.js 3.6.6 We move to the next cell and using the same reasoning, change 0 to 1.

3 of 18

Created with Fabric.js 3.6.6 In the next cell, we again change 0 to 1.

4 of 18

Created with Fabric.js 3.6.6 In the last cell of the first row, change 0 to 1.At this point, we have figured out that there is 1 path from the starting point to the end of the first row.

5 of 18

Created with Fabric.js 3.6.6 Now we will traverse through the first column.We will change the 1 to 0 in the current cell sincean obstacle is present and no valid paths canpass through this cell.

6 of 18

Created with Fabric.js 3.6.6 We will move downwards and will change 1 to 0 since the obstacle blocks any paths from going through this cell.

7 of 18

Created with Fabric.js 3.6.6 The only way to reach a cell is from the cell above it, or from the cell to its left.There is no cell to the left of the current cell, andthere are no paths to the cell above it (its value is 0).So, the last cell of the first column in unreachable.We set its value to 0.

8 of 18

Created with Fabric.js 3.6.6 Now cell (1, 1) is marked as 0, that is, it does not feature an obstacle. So, the number of ways to reach it will be the sum of the values in the cell above it and in the cell to its left.

9 of 18

Created with Fabric.js 3.6.6 The value of this cell was 1, that is, it has an obstacle. As the robot cannot pass through it, we have changed its value to 0.

10 of 18

Created with Fabric.js 3.6.6 Cell (1, 3) is 0, that is, it's free of obstacles. So, the number of ways to reach it will bethe sum of the values in the cell above it and in the cell to its left.

11 of 18

Created with Fabric.js 3.6.6 Cell (2, 1) is 0 so we can update its value to the sum of the value of cell above it and to its left.

12 of 18

Created with Fabric.js 3.6.6 Cell (2, 2) is 0, so, we can update its value to the sum of the value of cell above it and to its left.

13 of 18

Created with Fabric.js 3.6.6 Cell (2, 2) is 0, so, we can update its value to the sum of the value of cell above it and to its left.

14 of 18

Created with Fabric.js 3.6.6 Since the cell (3, 1) has an obstacle, we will set its value to 0.

15 of 18

Created with Fabric.js 3.6.6 Cell (3, 2) is 0 so we can update its value to the sum of the value of cell above it and to its left.

16 of 18

Created with Fabric.js 3.6.6 Cell (3, 3) is 0 so we can update its value to the sum of the value of cell above it and to its left.

17 of 18

Created with Fabric.js 3.6.6 The value of the last cell (3, 3) is 3, indicatingthat there are 3 distinct paths from start to finish.

18 of 18

Let’s implement the algorithm as discussed above:

Unique Paths to Goal using tabulation

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

The time complexity of this solution is O(m×n)O(m \times n), where mm and nn are the rows and columns for the input matrix.

Space complexity#

The space complexity of this solution is O(1)O(1), since we reuse the input array for dynamic programming. Therefore, no extra space is used.

Count Ways to Score in a Game

Nth Tribonacci Number